package com.qjc.demo.algorithm.链表中倒数第k个节点剑指offer22;

/**
 * @ClassName: Solution
 * @Author: qjc
 * @Date: 2023/8/23 10:45
 */
public class Solution {
    // 返回单链表中倒数第k个节点
    public static ListNode getKthFromEnd(ListNode head, int k) {
        // 以k=3为例说明
        // 先定义一个节点，该节点走到最后一个节点
        ListNode firstNode = head;
        // 再定义一个节点，距离第一个节点k个节点的位置，当第一个节点走到空节点的时候，该节点就是倒数第k个节点的位置
        ListNode secondNode = head;
        // 比如倒数第3个节点，那么第一个节点应该先走到第三个节点上
        for (int i = 0; i <= k - 1; i++) {
            firstNode = firstNode.next;
        }
        // 开始走第二个节点，从首节点开始紧跟着第一个节点走即可，第一个节点走到空节点的时候就结束
        while (firstNode != null) {
            firstNode = firstNode.next;
            secondNode = secondNode.next;
        }
        return secondNode;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;

        ListNode kthFromEnd = getKthFromEnd(head, 3);
        while (kthFromEnd != null) {
            System.out.println(kthFromEnd.val);
            kthFromEnd = kthFromEnd.next;
        }

    }

}
